package com.gwcloud.leetcode.interview100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/** 
* @ClassName   : Leetcode0103 
* @author      : ganwei 
* @date        : 2020年5月26日 
* @Description :  二叉树的锯齿形层次遍历 
*/
public class Leetcode0103 {
	List<List<Integer>> result = new ArrayList<>();
	/**
	 * -解题思路，
	 */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    	Queue<TreeNode> q = new LinkedList<TreeNode>();
    	q.offer(root);
    	boolean flag = true;
    	while(!q.isEmpty()) {
    		int length = q.size();
    		LinkedList<Integer> l = new LinkedList<Integer>();
    		for(int i = 0; i < length; i++) {
    			TreeNode node = q.poll();
    			if(flag) {
    				l.addFirst(node.val);
    			}else {
    				l.addLast(node.val);
    			}
    			
    			if(node.left != null) {
    				q.offer(node.left);
    			}
    			
    			if(node.right != null) {
    				q.offer(node.right);
    			}
    		}
    		result.add(l);
    		flag = !flag;
    	}
    	
    	return result;
    }
    public static void main(String[] args) {
    	
    }
}
